package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Dennis Li
 * @date 2020/9/8 11:25
 */
public class MergeKLists_23 {

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));

        for (ListNode node : lists) {
            while (node != null) {
                ListNode next = node.next;
                node.next = null;
                queue.offer(node);
                node = next;
            }
        }

        ListNode head = new ListNode(-1), cur = head;

        while (!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
        }

        return head.next;
    }

    public ListNode mergeKLists2(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int lo, int hi) {
        if (lo == hi) {
            return lists[lo];
        }
        if (lo > hi) {
            return null;
        }
        int mid = lo + (hi - lo) / 2;
        // 分治的考虑 -- 先将左半部分的全部排序
        ListNode left = merge(lists, lo, mid);
        // 再将右半部分全部排序
        ListNode right = merge(lists, mid + 1, hi);
        // 将左右两个头结点进行结合
        return mergeTwoLists(left, right);
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) return l1 != null ? l1 : l2;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
        }
        return l1.val < l2.val ? l1 : l2;
    }

}
